Educational Codeforces Round 73 Div2 A~D 题解

本场链接:Educational Codeforces Round 73

闲话

这场VP出了A~D.但是猜的成分挺高的.

A. 2048 Game

题目大意:给定一个nn个数的集合,保证其内所有的元素都是22的幂.每次你可以从中选出两个数,并把他们俩的和作为新元素放进原集合.而原来的两个数被删掉.问是否能出现2048.只用输出是否.

数据范围:
1n1001 \leq n \leq 100

思路

乱搞即可.规定一个目标,初始为2048,每次看目标的值的数量够不够,如果不够的话就把目标拆解一半,再算新的目标是否足够.注意如果原序列里有原来的目标值,则所需的数量会减少.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pil;
#define x first
#define y second
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		map<ll,int> cnt;
		for(int i = 1;i <= n;++i)	
		{
			ll x;scanf("%lld",&x);
			++cnt[x];
		}
		int target = 2048,ok = 0,need = 1;
		while(target >= 1)
		{
			if(cnt[target] >= need)	
			{
				// cout << target << " " << cnt[target] << endl;
				ok = 1;
				break;
			}
			need -= cnt[target];
			target /= 2;
			need *= 2;
			
		}
		if(!ok)	puts("NO");
		else puts("YES");
    }
    return 0;
}

B. Knights

题目大意:一个nnn*n的棋盘上放置若干个棋子,每个棋子是两种颜色中的一个.棋子按"日"字型攻击.构造一种摆放方案,使得整个棋局上颜色不同且可以互相攻击到的棋子对的数量最多.

思路

对于每一个点来说,如果他的八个方向的点都是跟他颜色不同的,则自然就是最多的.因此联想到二分图的染色,对这个图一样的处理,即使得颜色不同且互相攻击到的对数最多.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
char g[N][N];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= n;++j)
			if((i + j) & 1)	g[i][j] = 'W';
			else g[i][j] = 'B';
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j)
			printf("%c",g[i][j]);
		puts("");
	}
    return 0;
}

C. Perfect Team

题目大意:三种类型的零件各有a,b,ca,b,c个,一个机器里要有恰好三个零件,其中a,ba,b零件的数量不得少于11.问最多能组合出多少种.

思路

显然应该先满足cc的情况,在组合abcabc的前提下算出一个结果,之后问题就又等价成了只有abab的时候有多少种组合方式.由于此时a,ba,b的类型没有什么区别,因此可以交换使得aba \leq b.这个时候还有两种构造机器的方式:一种是aabaab另一种是bbabba.假设在最后的答案里,前者有xx个后者有yy个,那么显然答案就是x+yx+y,根据不等式关系有x+ya+b3x+y \leq \frac{a+b}{3}.但是答案不是直接加上这个数就结束了的,因为还有一个极端情况:如果此时b2ab \geq 2*a的话,原来的不等式的右侧就有:a+b33a3=a\frac{a+b}{3} \leq \frac{3a}{3} = a即此时如果选择aa答案可能会变得更好,这是一个特殊情况,需要额外考虑.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {	
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		int res = 0;
		res += min({a,b,c});
		a -= res;b -= res;c -= res;
		if(a > b)	swap(a,b);
		if(a * 2 <= b)
		{
			res += a;
			b -= a;
			a = 0;
		}
		else res += (a + b) / 3;

		printf("%d\n",res);
    }
    return 0;
}

D. Make The Fence Great Again

题目大意:有nn个元素,每个元素有两个属性aabb,bb表示如果要让aa增加11所要付出的代价.现在要使整个序列里不存在相邻的两个元素的aa值相同.问最小化费是多少.

思路

这个题一拿到手会发现非常像dpdp.但是由于数的范围会导致整个空间开不够,而且也不能靠滚动数组优化空间.因此思路就断了,如果继续想贪心构造会发现这个题也没什么突破口.dp关键的一个问题就是值域太大了,那么有没有办法使第二维的值域变小呢?答案是肯定的.
对于每个元素来说,他的aa值增加的次数是不超过22的,关于这一点可以手推验证.只要运用这个性质,就可以把第二维的空间压下来了.
状态:f[i][j]f[i][j]表示当前在ii元素上,这个元素要增加jj次.
入口:f[1][0]=0,f[1][1]=b[1],f[1][2]=2b[1]f[1][0] = 0,f[1][1] = b[1],f[1][2] = 2 * b[1]
转移:当且仅当a[i]+ja[i1]+ka[i] + j \neq a[i - 1] + k时,f[i][j]=min(f[i][j],f[i1][k]+jb[i])f[i][j] = min(f[i][j],f[i - 1][k] + j * b[i])
出口:min(f[n][0],f[n][1],f[n][2])\min({f[n][0],f[n][1],f[n][2]})
注意,本题的答案范围是2182^{18},这意味着要开LLLL.不过这还不是重点,重点是INFINFff数组的初值一定要根据类型设置大小,因为这里是LLLL所以设置的是2602^{60}如果开成2302^{30}就会WA.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 3e5+7,INF = (1ll << 60);
int a[N],b[N],f[N][3];
signed main()
{
    int T;scanf("%lld",&T);
    while(T--)
    {
		int n;scanf("%lld",&n);
    	for(int i = 1;i <= n;++i)	scanf("%lld%lld",&a[i],&b[i]);
		f[1][0] = 0;f[1][1] = b[1];f[1][2] = 2 * b[1];
    	for(int i = 2;i <= n;++i)
    		for(int j = 0;j <= 2;++j)
    		{
    			f[i][j] = INF;
				for(int k = 0;k <= 2;++k)
					if(a[i - 1] + k != a[i] + j)
						f[i][j] = min(f[i][j],f[i - 1][k] + j * b[i]);
    		}
    	printf("%lld\n",min({f[n][0],f[n][1],f[n][2]}));
    }
    return 0;
}